package leetcode.interview;
/*
统计一个数字在排序数组中出现的次数。



示例 1:

输入: nums = [5,7,7,8,8,10], target = 8
输出: 2
思路：递归二分法

 */
public class TestOffer5301 {
    int count=0;
    public int search(int[] nums, int target) {
        helper(nums,0,nums.length-1,target);
        return count;
    }

    public void helper(int[] nums,int start,int end,int target){
        if(start<=end){
            int mid=(start+end)/2;
            if(target==nums[mid]){
                count++;
                //特殊之处：分为两个区间继续查找
                helper(nums,start,mid-1,target);
                helper(nums,mid+1,end,target);
            }
            else if(target>nums[mid]){// 1    3【     9 】    target :4
                helper(nums,mid+1,end,target);//查找右侧
            }
            else {
                helper(nums,start,mid-1,target);//查找左侧
            }
        }
    }
}
